
#include <stdio.h>
#include <stdlib.h> /* for rand */

static void dbg_prn_arr(int * arr, int first, int last);


static void s_qsort(int * arr, int first, int last) {
    int i = first;
    int j = last;
    const int x = arr[(first + last) / 2];

    dbg_prn_arr(arr, first, last);

    while (i <= j) {
	while (arr[i] < x) { ++i; }
	while (x < arr[j]) { --j; }

	if (i > j) {
	    break;
	} else if (i < j) {
	    const int tmp = arr[j];
	    arr[j] = arr[i];
	    arr[i] = tmp;
	}
	++i;
	--j;
    }
    //fprintf(stdout, "i=%2d,j=%2d ", i, j);

    if (first < j) {
	s_qsort(arr, first, j);
    }

    if (i < last) {
	s_qsort(arr, i, last);
    }
}

#define ARR_SIZE (10)

#define DBG_ARR_ITER_MAX_COUNT (32)
static int g_dbg_arr_iter = 0;

static void dbg_prn_arr(int * arr, int first, int last) {
    int i;

    if (++g_dbg_arr_iter >= DBG_ARR_ITER_MAX_COUNT) {
	fprintf(stdout, "STOPPING - TOO MUCH ITERATIONS\n");
	exit(-1000);
    }

    fprintf(stdout, "[%d/%d]", first, last);
    for (i = 0; i < ARR_SIZE; ++i) {
	fprintf(stdout, " %d", arr[i]);
    }

    fputs("\n", stdout);
}

static int dbg_chk_arr(int * arr) {
    int ok = 0;
    int i;
    
    for (i = 0; i < ARR_SIZE; ++i) {
	if (arr[i] != i) {
	    ok = -(i + 1);
	    break;
	}
    }

    g_dbg_arr_iter = 0;

    fprintf(stdout, "%s\n\n",
	    (ok == 0) ? "ok - array sorted" : "ARRAY UNSORTED");
    return ok;
}

static void dbg_arr_shuffle(int * arr) {
    const int SHUFFLE_COUNT = 10;
    int i;
    int j;
    for (i = 0; i < ARR_SIZE; ++i) { arr[i] = i; }

    for (i = 0; i < SHUFFLE_COUNT; ++i) {
	for (j = 0; j < ARR_SIZE; ++j) {
	    const int shuffle_index = rand() % ARR_SIZE;
	    const int tmp = arr[j];
	    arr[j] = arr[shuffle_index];
	    arr[shuffle_index] = tmp;
	}
    }
}

#define SHUFFLE_TEST_COUNT (7)

int main() {
    int arr[ARR_SIZE];
    int i;
    int ok;

    // test sorted array
    for (i = 0; i < ARR_SIZE; ++i) {
	arr[i] = i;
    }
    s_qsort(arr, 0, ARR_SIZE-1);
    ok = dbg_chk_arr(arr);

    // test array sorted in the reverse order
    for (i = 0; i < ARR_SIZE; ++i) {
	arr[i] = ARR_SIZE - i - 1;
    }
    s_qsort(arr, 0, ARR_SIZE-1);
    ok = dbg_chk_arr(arr);

    for (i = 0; i < SHUFFLE_TEST_COUNT; ++i) {
	fprintf(stdout, "shuffle # %d\n", i);
	dbg_arr_shuffle(arr);
	s_qsort(arr, 0, ARR_SIZE-1);
	ok = dbg_chk_arr(arr);
    }

    fprintf(stdout, "%s\n", ok == 0 ? "ALL OK" : "UNSORTED ARR FOUND");

    return ok;
}
